package Algorithm.RecursionAndRecurrence;

import java.util.Arrays;
import java.util.Scanner;
public class Recursion {


    //TODO:92. 递归实现指数型枚举
    // 从 1∼n,n个整数中随机选取任意多个，输出所有可能的选择方案。（每个数字独立选择选/不选）（2^n种选择方案）
    //输入格式:
    //输入一个整数 n
    //输出格式:
    //每行输出一种方案。
    //同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。对于没有选任何数的方案，输出空行。
    //本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
    //数据范围
    //1≤n≤15
    static int[] str1 = new int[15];
    public static void dfs(int n){
        int u = 15;

        if(n > u){
            System.out.println("超限了");
//            return -1;//超限
        }

        //找到边界如何处理
        if(n == 0){
            for(int i = 0; i < 15; i++){
                if(str1[i] == 1) {
                    System.out.print(i + " ");

                }
                System.out.println();
            }
            return;
        }

        //处理分支
        str1[n] = 1;//分支1：要这个数字，给下一个看的
        dfs(n - 1);//这个的用法是找边界，我一开始想的是减法，减 1 减到 0 ，那么上面的就要修改为 n == 0；
        str1[n] = 0;//还原现场，这个是往上一级看的

        str1[n] = 2;//分支2：不要这个数字，给下一个看的
        dfs(n - 1);
        str1[n] = 0;//还原现场，这个是往上一级看的

    }



    //TODO:94. 递归实现排列型枚举
    // 把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。（全排列）（n个元素的排列数（n!））
    //输入格式
    //一个整数 n
    //输出格式:
    //按照从小到大的顺序输出所有方案，每行 1 个。
    //首先，同一行相邻两个数用一个空格隔开。
    //其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
    //数据范围:
    //1≤n≤9
    //输入样例：
    //3
    //输出样例：
    //1 2 3
    //1 3 2
    //2 1 3
    //2 3 1
    //3 1 2
    //3 2 1
    int n = 0;
    int[] str2 = new int[9];
    boolean[] Judgment = new boolean[9];//开关数组：True为已用过，False
    public void dfs2(int N){
//        final int X = N;
//        System.out.println(Arrays.toString(Judgment));
        //边界
        if(N == 0){
            for(int i = 0; i < 9; i++){
                if(str2[i] != 0) {
                    System.out.print(str2[i] + " ");
                }
            }
            System.out.println();
            return;
        }

        //分支
        for(int i = 0; i < 9; i++){
            if(!Judgment[i]){
                Judgment[i] = true;
                str2[i] = i + 1;
                dfs2(N - 1);

                //恢复现场
                Judgment[i] = false;
                str2[i] = 0;
            }
        }
    }




    //TODO：93. 递归实现组合型枚举从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。（组合）
    //输入格式：
    //两个整数 n,m ,在同一行用空格隔开。
    //输出格式：
    //按照从小到大的顺序输出所有方案，每行 1 个。
    //首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
    //其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。
    //数据范围
    //n>0 , 0≤m≤n , n+(n−m)≤25
    //输入样例：
    //5 3
    //输出样例：
    //1 2 3
    //1 2 4
    //1 2 5
    //1 3 4
    //1 3 5
    //1 4 5
    //2 3 4
    //2 3 5
    //2 4 5
    //3 4 5
    //TODO:① n 个位置
    // ②当前该枚举哪个位置 ， u
    // ③strat,当前最小可以以哪个元素枚举
    int start = 1;
    int[] str3 = new int[30];

    //递归里面做不了保存：从 1 ~ n 的 n 只能额外保存
    public void dfs3(int u,int N){        //边界
        if(u == 0){
            for(int i = 0; i < 25; i++){
                if(str3[i] != 0) {
                    System.out.print(str3[i] + " ");
                }
                System.out.println();
            }
            return;
        }

        //顺序
        for(int i = start; i <= N; i++){

            start = start + 1;
            str3[i] = i;
            dfs3(u - 1,N);

            //恢复现场
            str3[i] = 0;
            u = u + 1;
            start = start - 1;
        }

    }
}
